package com.mdnote.practice.tire;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/24
 * @description 单词搜索
 */
public class LeetCode79 {



    public static void main(String[] args) {
        char[][] board = {
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        };


        LeetCode79 leetCode79 = new LeetCode79();
        System.out.println(leetCode79.exist(board, "ABCC"));
    }

    private static boolean isFinish = false;

    private int[] dx = {-1, 1, 0,  0};
    private int[] dy = { 0, 0, 1, -1};

    public boolean exist(char[][] board, String word) {
        // 使用DFS
        // 先对boardboard进行遍历
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0) && !isFinish) {
                    // 进行DFS
                    isFinish = dfs(1, i, j, board, word);
                }
            }
        }

        return isFinish;
    }

    public boolean dfs(int level, int start_row, int start_column, char[][] board, String word) {
        // Terminator
        if (level == word.length()) {
            return true;
        }
        // Process current logic
        char temp = board[start_row][start_column];
        boolean isFinish = false;

        // drill down
        board[start_row][start_column] = '@';

        for (int i = 0; i < dx.length; i++) {
            if (start_row + dx[i] >= 0 && start_row + dx[i] < board.length &&
                    start_column + dy[i] >= 0 && start_column + dy[i] < board[0].length &&
                    board[start_row + dx[i]][start_column + dy[i]] == word.charAt(level) && !isFinish) {

                isFinish = dfs(level + 1, start_row + dx[i], start_column + dy[i], board, word);

            }
        }
        // restore current data
        board[start_row][start_column] = temp;

        return isFinish;
    }
}
